class Solution {
    int MOD = (int)1e9+7;
    int[][][] dp;
    int limit;
    public int numberOfStableArrays(int zero, int one, int limit) {
        int max = Math.max(zero,one);

        //注意这里这个数组要开zero和one的最大值
        //直接用201 201 201的话，跑到60来个用例就会超时
        //用HashMap，将三者拼接成字符串的key value也会超时，建议这样开dp数组
        dp = new int[max+1][max+1][limit+1];
        for(int i=0;i<=max;i++){
            for(int j=0;j<=max;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }


        this.limit = limit;
        return dfs(zero,one,0);
    }
    public int dfs(int i,int j,int count){
        if(i==0&&j==0){
            return 1;
        }
        if(i<0||j<0){
            return 0;
        }
        if(dp[i][j][count]!=-1){
            return dp[i][j][count];
        }
        int ans;
        if(count==limit){
            ans = dfs(j-1,i,1)%MOD;
        }else {
            ans =  (dfs(i-1,j,count+1)%MOD+dfs(j-1,i,1)%MOD)%MOD;
        }
        dp[i][j][count] = ans;
        return ans;
    }
}

